栈是限定在尾部进行插入或删除的线性表。表尾称为栈顶（top），表头称为栈底（base）。栈的修改按照后进先出的原则。
栈有两种存储表示方法：顺序栈和链栈。顺序栈是利用一组连续存储单元依次存放栈底到栈顶数据元素的位置。链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
注意：
1.如果在函数中需要修改形参，而且希望函数结束后变量修改生效，可以使用引用的方法。例如把栈顶元素传给e的函数：int Pop(Stack &s,int &e)，在函数中我们需要把栈顶元素传给e，并且删除栈顶，如果直接int Pop(Stack s,int e)，传递的只是实参的副本，不能修改实参。
2.指针变量做形参时，若要修改它指向的地址，则需要使用引用，如果修改其地址中的参数比如value、next等，可以不使用引用。
一、顺序栈
1.用数组实现顺序栈
这种方式直接用数组存储栈中的内容，用top记录栈顶在数组中的位置。通过移动top完成各种操作。栈为空时，top=-1，此后每添加一个元素，top++，每取出一个元素，top下移表示删除栈顶，实际上元素还在数组中。
#include<iostream>
#define MAX 100//定义数组长度
using namespace std;
struct Stack//建立栈
{
int value[MAX];
int top;//栈顶的数组序号
};
void Init(Stack &s)//初始化栈
{
s.top=-1;
}
int Push(Stack &s,int e)//把元素e压入栈顶
{
if(s.top>MAX-1)//如果超出栈的容量，返回0
return 0;
s.top++;//栈顶加1
s.value[s.top]=e;//把e赋给栈顶
return 1;
}
int IsEmpty(Stack s)//判定栈是否为空
{
if(s.top==-1)
return 1;
else
return 0;
}
<pre name="code" class="cpp">
<span style="font-family: Arial, Helvetica, sans-serif;">int Push(Stack &s,int e)</span><span style="font-family: Arial, Helvetica, sans-serif;">//取出栈顶元素，删除栈顶</span>
{
if(s.top==-1)
return 0;
e=s.value[s.top];s.top--;//栈顶序号-1表示删除栈顶
}
int main(){
Stack sqstack;
Init(sqstack);
cout<<"输入一串整数（输入非数字结束）："<<endl;int e;while(cin>>e)//将输入值依次压入栈顶Push(sqstack,e);while(!IsEmpty(sqstack))//若栈不为空，依次输出栈
{
Pop(sqstack,e);
cout<<e<<" ";
}
return 0;
}
2.顺序栈的一般实现
这种实现方式设置栈顶top和栈底base，栈为空时top和base重合，插入一个元素top加1，取出一个元素top减1。非空栈的栈顶指针始终位于栈顶元素的下一个位置。这种方法可以不指定栈的长度，设置一个基本容量和增量，先分配基础容量，栈的空间不够时，再增加容量。
程序采用C语言中的malloc分配内存，于是可以使用realloc给malloc分配好的内存增加容量。但C++中常用的new和delete不能追加容量。
#include<iostream>
#define SIZE 100//基础容量
#define dtSIZE 10//附加容量（可多次扩容）
using namespace std;
struct SqStack
{
int *top;//栈顶指针
int *base;//栈底指针
int size;//栈的当前容量
};
void Init(SqStack &s)//初始化栈
{
s.base=(int *)malloc(SIZE*sizeof(int));
//s.base=new int [SIZE];//使用new不能追加空间
if(!s.base) exit(-1);//内存分配失败
s.top=s.base;
s.size=SIZE;
}
int Push(SqStack &s, int e)//把元素e压入栈顶
{
if(s.top-s.base>s.size)//栈满，追加dtSIZE大小的空间
{
s.base=(int *)realloc(s.base,(s.size+dtSIZE)*sizeof(int));
if(!s.base)exit(-2);//内存分配失败
s.size=s.size+dtSIZE;
}
*s.top=e;//把e赋给栈顶
s.top++;//栈顶指针+1
return 1;
}
int Pop(SqStack &s,int &e)//取出栈顶元素，并删除栈顶
{
if(s.top==s.base)//top与base重合时，栈为空
return 0;
s.top--;//top先减1，再取元素
e=*s.top;
return 1;
}
int IsEmpty(SqStack s)//判空
{
if(s.top==s.base)
return 1;
else
return 0;
}
void Destroy(SqStack &s)//销毁栈
{
free(s.base);
//delete s.base;//如果使用new分配内存，则用delete删除。
}
int main()
{
SqStack slist;
Init(slist);
cout<<"输入一串数字，（以非数字结束）："<<endl;
int e;
while(cin>>e)
{
Push(slist,e);//将读取的数字压入栈顶
}
while(!IsEmpty(slist))//栈不为空时
{
Pop(slist,e);//取出栈顶元素，并删除栈顶
cout<<e<<" ";
}
Destroy(slist);
return 0;
}
二、链栈
链栈的结构与链表相似，只是插入与删除等操作都在链表的头部，即链栈是一个以top为头结点，从栈顶指向栈底的单链表。
#include<iostream>
using namespace std;
struct ListStack
{
int value;
ListStack *next;
};
void Init(ListStack *s)//初始化
{
s->next=NULL;//栈顶指针下一个置空表示栈为空
}
void Push(ListStack *s,int e)//把元素e压入栈顶
{
ListStack *p;
p=new ListStack;
p->value=e;
p->next=s->next;
s->next=p;
}
int Pop(ListStack *s,int &e)//把栈顶元素取出赋给e，并删除栈顶
{
ListStack *delete_r;
if(s->next==NULL)
return 0;
else
{
delete_r=s->next;
e=s->next->value;
s->next=delete_r->next;
delete delete_r;
}
}
void Destroy(ListStack *s)//销毁栈
{
ListStack *delete_q;
while(s->next!=NULL)
{
delete_q=s->next;
s->next=s->next->next;
delete delete_q;
}
}
int IsEmpty(ListStack *s)//判空
{
if(s->next==NULL)
return 1;
else
return 0;
}
int main()
{
ListStack *slist;
slist=new ListStack;
Init(slist);
int e;
while(cin>>e)
Push(slist,e);
while(!IsEmpty(slist))
{
Pop(slist,e);
cout<<e<<" ";
}
Destroy(slist);
return 0;
}
本页共191段，3754个字符，5827 Byte(字节)